One of the most significant functions performed by routers is the IP lookup. Presently the majority of routers forward IPv4 (IP version 4) packets, but increasing numbers are now also forwarding IPv6 (IP version 6) packets. IPv6, mainly introduced to alleviate the address shortage of IPv4, uses 128 bit addresses. When a packet arrives, the router must search a forwarding table using the IP address and determine which entry in the table represents the best route for the packet to take to reach its destination. The IP address scheme is hierarchical in that it uses the concept of variable-length prefixes e.g., roots and branches. Entries in the table represent prefixes and have variable lengths. The use of prefixes introduces a new dimension in that multiple entries (prefixes) may represent valid routes to the same destination. If a packet matches multiple prefixes, it is intuitive that the packet should be forwarded corresponding to the most specific prefix, also known as the longest matching prefix. Therefore, unlike a simple search that seeks to find an exact match within a table, these lookups must find the most specific route from a number of entries, i.e., the route that represents the best network prefix for the given address (the longest prefix matching or LPM for short).
There are two techniques for addressing the LPM problem. The first technique is based on converting the longest matching prefix problem into a series of exact matches, and the second technique is based on performing a series of incremental matches using a data structure called a tree (or trie). The first technique will be discussed in more detail below. A tree is a data structure which allows for an incremental search by matching one or more bits of a key at a time. A tree is a collection of nodes, each node containing a table of pointers. One solution for IPv4 forwarding lookups uses a binary tree, in which each tree node is a table consisting of two pointers. To find the best matching prefix in the tree, successive bits of the address are used to follow a path through the tree, starting from the root node (top most node), until the longest matching prefix is found. Thus the performance of a tree can depend directly on the number of bits in the address, the number of bits used at each incremental step, and the number of entries in the routing table.
Since the present invention makes use of the previously mentioned technique of converting a best matching prefix problem into an exact match problem it will be discussed in more detail. In this technique, the forwarding table is divided into several (at most 32 in IPv4) logically separate forwarding tables such that table i contains all the prefixes of length i. In other words, prefix 1* is in the length 1 table, prefix 10* is in the length 2 table, and so on. Using a linear search, a longest prefix match is performed by starting with the longest length prefix table and working backwards until it finds a table that contains a matching prefix. Each search through a table requires an exact match (unlike finding the best or longest matching prefix). As this algorithm uses a linear search it can cost up to 32 exact matches for IPv4 and 128 exact matches for IPv6 in the worst case scenario.
A good technique to use for finding an exact match is hashing. A hash function is a sort of compression algorithm that is used to condense a key into a smaller sized field which can be used as an index into a table. Because of the nature of compression, hashing inevitably encounters the problem of collision (i.e., different keys result in a same hashed value). Higher compression ratios result in higher occurrences of hash collisions. Hashing operates strictly on an exact-match basis, thus a hash lookup can only search for prefixes of a given length.
Despite the ability of being able to search all the entries of a single prefix length in a single hash lookup, the above technique could still need to perform this lookup for every possible prefix length in order to find the LPM. Hence, this could require up to 32 hash lookups for IPv4, and 128 for IPv6. This performance is inadequate.
U.S. Pat. No. 6,018,524 Jan. 25, 2000 Turner et al describes an algorithm for improved binary search which is applied to IP LPM. This algorithm is an improvement to the previously described linear search over a set of hash tables. This improvement is achieved by replacing the linear search with a binary search. This allows the number of potential prefix lengths to be cut in half after each step of the search. Compared to the linear search, which is only able to eliminate a single prefix length at a time, this is a significant improvement. To facilitate a binary search, the algorithm must insert markers into the logical prefix length tables in order to indicate that there is a potentially longer matching prefix when there are no prefixes at the current level that share the same root. To contrast with the present invention which will be described in detail below, this search is called the serial binary search in this specification.
FIG. 1 shows an example of this algorithm. In this figure, there are seven logical bins. Each bin would contain all the prefixes of a particular length. The binary search starts at the midpoint of the search range, in this case at Bin 4. In this example, at Bin 4 the search returned either a marker or a match on the prefix. In either case, the result of the match would be stored as the best possible prefix. The search then proceeds to Bin 6, the midpoint of the remaining bins. Here, the search fails to find either a marker or a matching prefix so the range is reduced to the set of bins with prefixes shorter than those between Bin 4 and Bin 6. At Bin 5, the search is successful and the result is the best possible match. In this figure the numbers below the bins show the number of memory accesses required to find an entry in that bin.
In the worst case, this binary search on prefixes would require log2(W) serial memory accesses (memory reads or probes), where W is the number of unique prefix lengths in bits This performance is already better than the majority of LPM algorithms.
As mentioned previously, IPv6 has recently been introduced to alleviate the address shortage of IPv4, and uses 128 bit addresses. The dramatic increase in the address length makes it difficult for many existing IPv4 lookup algorithms to simply scale up to IPv6. Using algorithms that are currently used for IPv4 to implement IPv6 forwarding would likely result in an explosion in the size of routing table data structures, and an increase in the number of memory accesses needed to perform the lookup. Fortunately, IPv6 makes use of hierarchical addressing which is intended to simplify the routing tables of IPv6 routers. Without hierarchical addressing, IPv6 routing tables would be reduced to the swamp of prefixes that exist today in IPv4.
Presently, the majority of allocated IPv6 prefixes are longer than 16 bits, and usually share a common prefix (0x2001, 0x2002, and 0x3FFE). Because of this, techniques used to accelerate IPv4 lookups, such as doing an initial lookup of the first 16 bits of an address will likely only ever return one of a few possible results at best. This single memory access is difficult to justify as it simply selects between one of the small number of entries, and the memory required to support this lookup is large.
As routers forward at higher speeds, the efficiency of the forwarding algorithm can make a significant impact on the performance of the system. More efficient algorithms will allow higher line rates to be achieved.
To simplify the description of the invention, following terms are roughly defined.
Bin: A logical table containing entries for IPv6 prefixes which all have the same length. The number of bins equals the number of unique prefix lengths. Possible implementations of a bin could include an individual hash table for a bin, or a single large hash table containing all bins such that a portion of the hash key contains some reference to the bin.
Ideal Asymmetric Search: A search in which every search instance in a parallel LPM search has the same worst case search time. This requires that each search range is sized appropriately to distribute the gains of the LPM improvements over the search ranges. An ideal asymmetric search results in a search that is able to examine the largest number of bins, given a fixed number of search instances, and latency budget.
Marker: An entry in a bin which does not represent a prefix. Instead, the entry indicates that there is a longer prefix with the same root. A marker may also contain a pointer to the next-hop information of the longest prefix sharing the same root as the marker, if such a prefix exists.
Range Truncation: A process that takes an ideal asymmetric search ranges and shortens it to a usable size (128 or 32 bins) in such a way as to not break up sub-ranges which may be ideally searched.
Root: A portion of a prefix that is common with that of another prefix. In other words, a prefix of prefixes.
Steal: A process, in parallelized LPM searches in which a search instance redistributes other search instances, which were previously searching shorter prefix lengths, along its remaining search range.